// Matrix01.cpp : Defines the entry point for the console application.
//
/*
1. You're given a matrix. For example:

1 0 0

0 0 0

2 0 0

For a matrix as above, each number represents a city. 1 means the start city, 2 means the finish city, 0 means the city needs to be visited, 3 means that the city is not accessible.

You're asked to travel from the start city, visit all accessible cities once and only once and exit from the finish city. You can move horizontally or vertically only.  Also you can only move from a city to another city that is next to it (no teleport).

Write a program to print the number of unique ways to traverse the matrix.  For example, for the matrix given above, the output should be 2 since there're only 2 distinct ways to visit the matrix. (See below and follow the order of numbers). Please note, the program only needs to output 2 and is not required to print out all paths.

1 2 3

8 7 4

9 6 5

1 4 5

2 3 6

9 8 7

Choose any programming language.  The final test is to use the matrix below (a 7 X 8 matrix) as the input.

1 0 0 0 0 0 0

0 0 0 0 0 0 0

0 0 0 0 0 0 0

0 0 0 0 0 0 0

0 0 0 0 0 0 0

0 0 0 0 0 0 0

0 0 0 0 0 0 0

2 0 0 0 0 3 3

*/

#include "stdafx.h"
#include <Windows.h>
#include <string>
#include <vector>
using namespace std;
enum VISIT_RESULT
{
    visit_SUCCEED = 0,
    visit_VISITED,
    visit_NONACCESSIABLE,
    visit_COMPLETE
};

enum MOVE_DIRECTION
{
    GORIGHT =0,
    GOLEFT = 1,
    GOUP,
    GODOWN
};

#define GENERAL_CITY                   0
#define  START_CITY                        1
#define  EXIT_CITY                           2
#define  UNACCESSIABLE_CITY       3

#define  MAX_ROW                    7
#define  MAX_COLUMN              8
//As input matrix, there are 2 unaccessible cities;
#define  NEED_VISIT                   MAX_ROW * MAX_COLUMN - 2    
int Metrix[7][8]=
{
    1, 0, 0, 0, 0, 0, 0, 2,
    0, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 3, 3
};

typedef struct _CityNode
{
    int nX;
    int nY;
    int nType;
    BOOL bVisited;
    _CityNode()
    {
        nX = 0;
        nY = 0;
        nType = 0;
        bVisited = FALSE;
    }
    _CityNode(int xPos, int yPos, int nCityType, BOOL bIsVisited = FALSE)
    {
        nX = xPos;
        nY = yPos;
        nType = nCityType;
        bVisited = bIsVisited;        
    }

    VISIT_RESULT VisitCity()
    {
        if (nType == UNACCESSIABLE_CITY)
        {
            return visit_NONACCESSIABLE;
        }
        if (bVisited)
        {
            return visit_VISITED;
        }
        bVisited = TRUE;
        TCHAR szDebugInfo[255 + 1] = {0};
        _stprintf_s(szDebugInfo, 255, L"Visit City, coordinates: (%d, %d), City type: %d \n", nX, nY, nType);
        //OutputDebugStr(szDebugInfo);    

        if (nType == EXIT_CITY)
        {
            return visit_COMPLETE;
        }
        return visit_SUCCEED;
    }


 

} CityNode, *PCityNode;

CityNode cityMetrix[MAX_ROW][MAX_COLUMN];

typedef vector<PCityNode> Vect_CityArray;


PCityNode GotoNextCity(CityNode* pCurrentCity,  MOVE_DIRECTION moveDirection)
{
    if (NULL == pCurrentCity)
    {
        return FALSE;
    }
    int nX = pCurrentCity->nX;
    int nY = pCurrentCity->nY;

    PCityNode pNextCity = NULL;
    switch(moveDirection)
    {
    case GOUP:
        if (nX - 1 >=0)
        {
            pNextCity = &cityMetrix[nX -1][nY];
        }

        break;
    case  GODOWN:
        if (nX + 1 < MAX_COLUMN )
        {
            pNextCity = &cityMetrix[nX+ 1][nY];
        }
        break;
    case  GOLEFT:
        if (nY - 1 >= 0)
        {
            pNextCity = &cityMetrix[nX][nY - 1];
        }
        break;
    case GORIGHT:
        if (nY + 1 < MAX_COLUMN)
        {
            pNextCity = &cityMetrix[nX][nY + 1];
        }
        break;
    }
    
    return pNextCity;
}

void InitializeCityInfo()
{
    for (int iRow = 0; iRow< MAX_ROW; iRow++)
    {
        for (int iColumn = 0; iColumn< MAX_COLUMN; iColumn ++)
        {
            cityMetrix[iRow][iColumn].bVisited = 0;
            cityMetrix[iRow][iColumn].nType = Metrix[iRow][iColumn];
            cityMetrix[iRow][iColumn].nX = iRow;
            cityMetrix[iRow][iColumn].nY = iColumn;
        }
    }
}




void BackTracking(int nBackTrackingSteps, Vect_CityArray& steps)
{
    if (nBackTrackingSteps > steps.size())
    {
        return;
    }
    Vect_CityArray::iterator itor = steps.end() - nBackTrackingSteps;

//     for (; itor != steps.end(); itor++)
//     {
//         (*itor)->bVisited =FALSE;
//     }
    for (int i = 0; i< nBackTrackingSteps; i++)
    {
        
        steps.pop_back();
    }
}

void TraversingCity(PCityNode pCity, Vect_CityArray& path)
{
    if (NULL == pCity)
    {
        return ;
    }

    VISIT_RESULT visitResult =pCity->VisitCity();
    path.push_back(pCity);
   
   
    if (visitResult == visit_COMPLETE)
    {
         if (path.size() == NEED_VISIT)
         {
             _tprintf_s(L"Succeed, The path is :\n");
             wstring strFinalPath;
             for (int i = 0; i< (int)path.size(); i++)
             {
                 TCHAR czStep[20 + 1] ={0};
                 _stprintf_s(czStep, 20, L"[%d, %d]-->", path[i]->nX, path[i]->nY);
                 strFinalPath += czStep;
             }
             _tprintf_s(strFinalPath.c_str());
             BackTracking(path.size() - 1, path); // Back to start city, calculate next path;
         }
         else
         {
             //Back to previous city
              BackTracking(1, path);
         }
         return;
    }


    for (int i = 0; i<4; i++)
    {
        int e_direction = GORIGHT + i;
        int nCurentStep = path.size();
        PCityNode pNext = GotoNextCity(pCity, (MOVE_DIRECTION)e_direction);
        if ( pNext != NULL)
        {
            if (pNext->bVisited || pNext->nType == UNACCESSIABLE_CITY)
            {
                continue;
            }

            //  path.push_back(pNext);
            TraversingCity(pNext, path);
            BackTracking(path.size() - nCurentStep, path);
        }
    }
    

}

int _tmain(int argc, _TCHAR* argv[])
{
    Vect_CityArray vectPath;
    InitializeCityInfo();
 
    PCityNode pStart = &cityMetrix[0][0];
    
    TraversingCity(pStart, vectPath);
	return getchar();
}

